#include <stdio.h>
#include <stdlib.h>

struct list 
{
  int num;
  struct list * prev;
  struct list * next;
};

struct list * creat()
{
  struct list * head, * src, * des;
  int value, cycle = 1;

  head = (struct list *) malloc (sizeof(struct list));

  src = head;

  printf("input the data:\n");
  while (cycle) {    
    scanf("%d", & value);
    if (value != 0) {
      des = (struct list *) malloc (sizeof(struct list));
      des->num = value;
      printf(" %d ", des->num);
      src->next = des;
      des->prev = src;
      src = des;
    }
    else
      cycle = 0;
  }
  head = head->next;
  head->prev = NULL;
  src->next = NULL;

  printf("\n head : %d ", head->num);
  return head;
}

void display(struct list * head)
{
  struct list * src;

  src = head;
  if (head != NULL) {
    while (src != NULL) {
      printf(" %d ", src->num);
      src = src->next;
    }
  }
  printf("\n");
}

struct list * delete(struct list * head, int value)
{
  struct list * src;

  src = head;
  while (value != src->num && src->next != NULL)
    src = src->next;

  if (value == src->num) {
    if (src == head) {
      head = head->next;
      head->prev = NULL;
      free(src);
    }
    else if (src->next == NULL) {
      src->prev->next = NULL;
      free(src);
    }
    else {
      src->next->prev = src->prev;
      src->prev->next = src->next;
	  free(src);
    }
  }
  else
    printf(" %d could not been found!\n", value);

  return head;
}

struct list * insert(struct list * head, int value)
{
  struct list * src, * des;
  
  src = head;
  des = (struct list *) malloc (sizeof(struct list));
  des->num = value;

  while (des->num > src->num && src->next != NULL) {
    src = src->next;
  }
  if (des->num <= src->num) {
    if (head == src) {	// 插开关
      des->next = src;
      src->prev = des;
      head = des;
    }
    else {	// 插中间
      src->prev->next = des;
      des->next = src;
      des->prev = src->prev;
      src->prev = des;
    }
  }
  else {	// 插末尾
    src->next = des;
    des->prev = src;
    des->next = NULL;
  }

  return head;
}

int main()
{
  struct list * head;
  int value;

  head = creat();
  printf("input the number to be inserted:\n");
  scanf("%d", & value);
  
  head = insert(head, value);
  display(head);

  head = delete(head, 3);
  display(head);
}
